package com.adee.algorithm.graph;

// 图的另一种表示方法：邻接表
// 1.创建顶点类
class VNode {
    int data;  // data表示顶点下标
    VNode next; // 链表下一个元素
    public VNode() {

    }

    public VNode(int data) {
        this();
        this.data = data;
    }
}

// 2.定义一个图类
class Graph {
    public static final int NODE_COUNT = 5;  // 顶点总数量

    // 3.构造一个数组，数组的每个位置下标表示一个顶点，位置上放的是一个链表，链表上每个元素表示当前顶点直接指向的顶点
    VNode[] adjList = new VNode[NODE_COUNT];

    // 4.初始化图
    public Graph() {
        for (int i = 0; i < adjList.length; i++) {
            adjList[i] = null;
        }
    }
    // 5.构建图，按照模拟图给adjList每个位置填充元素
    public void build() {
        // A B C D E 编号 0 1 2 3 4
        // 顶点A，即adjList[0]位置新增出Node B C D
        add(0, new int[]{1, 2, 3});
        // 顶点B
        add(1, new int[]{3, 4});
        // 顶点C
        add(2, new int[]{3});
        // 顶点D
        add(3, new int[]{4});
        // 顶点E，null，没有指向的其他顶点

    }

    public void print() {
        for (int i = 0; i < adjList.length; i++) {
            StringBuilder sb = new StringBuilder();
            for (VNode n = adjList[i]; n != null; n = n.next) {
                sb.append(n.data).append("\t");
            }
            String s = sb.toString();
            System.out.println((s.length() == 0 ? "null" : s) + "\tod=" + getOD(i));
        }
    }

    // 给src顶点添加一个dest顶点
    public void add(int src, int dest) {
        VNode srcNode = adjList[src];
        VNode newNode = new VNode(dest);
        // newNode插入链表，采用头插法
        if (srcNode == null) {
            adjList[src] = newNode;
        } else {
            newNode.next = srcNode;
            adjList[src] = newNode;
        }
    }

    public void add(int src, int[] destList) {
        for (int i = 0; i < destList.length; i++) {
            add(src, destList[i]);
        }
    }

    // 获取某个顶点的出度OD
    public int getOD(int nodeIndex) {
        int od = 0;
        for (VNode n = adjList[nodeIndex]; n != null; n = n.next) {
            od++;
        }
        return od;
    }


}

public class Test002_adjacency_table {
    public static void main(String[] args) {
        Graph g = new Graph();
        g.build();
        g.print();
    }
}
